#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        //实现O(logn)的代码
        //使用二分查找
        int left = 0;
        int right = nums.size() - 1;
        int index = 0;
        while (left <= right)
        {
            int mid = (left + right) >> 1;
           
            if (nums[mid] > nums[left] && nums[mid] > nums[right])
            {
                left = mid;
            }
            else if (nums[mid] < nums[left] && nums[mid] < nums[right])
            {
                right = mid;
            }
            else
            {
                right--;
            }
        }
        index = left;
        int t;
        if ((t = func(nums, 0, index, target)) != -1)
        {
            return t;
        }
        if ((t = func(nums, index + 1, nums.size() - 1, target)) != -1)
        {
            return t;
        }
        return -1;
    }
    //使用二分查找某个数
    int func(vector<int> &nums, int left, int right, int target)
    {
        while (left <= right)
        {
            int mid = (left + right) >> 1;
            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
        }
        return -1;
    }
};

int main()
{
    Solution S;
    vector<int> nums = {2, 3, 4, 5, 1};
    cout << S.search(nums, 1) << endl;
}